/*
题目: 利用 rand7() 生成 rand10()
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

https://leetcode.cn/problems/implement-rand10-using-rand7/
 */
public class Rand10 {
    /*
    下面将需要生成的随机数中最大值记为n

    先去生成一个等概率产生0和1的方法：rand2() 。
        实现：调用 rand7() ，1,2,3 返回 1
                           4,5,6 返回 2
                               7 重来。

    将n转为二进制，看看是几位的二进制。
        例如本题的 10 ，二进制为 1010 。也就是说仅仅需要4位二进制数就能表示10进制的10。 用这个 rand2() 方法生成n的每个二进制位。

    创建一个数为 rand2() ，每次左移一位再加 rand2() 。

    如果出现不符合题意的情况，再次调用 rand10() 。
    */
    public int rand10() {
        // 只需要生成 [1, 10] 中的随机数, 而 10 只有 4 个比特位
        // 只需要利用 rand2 生成 4 个比特位
        int ret = 0;
        for (int i = 0; i < 4; i ++) {
            int rom = rand2();
            ret = (ret << 1) + rom;
        }
        // 满足则生成, 否则重来
        return ret <= 10 && ret != 0 ? ret : rand10();
    }

    // 生成 二进制 中的一位
    private int rand2() {
        // 先利用 7 生成一个 随机数
        int random = rand7();
        // 可以控制随机 生成 0 或者 1
        return random == 7 ? rand2() : random % 2;
    }
}
